package problem_62;

import java.util.Map.Entry;
import java.util.TreeMap;
import utils.ArrayList;
import utils.Digits;
import utils.IPrimes;
import utils.PrimesFactory;

/**
 * @author wolfgang
 * @note Find the smallest cube for which exactly five permutations of its digits are cube.
 */
public class Problem62 {

	// store the primes for the hash function for quick and easy access
	long _primes[];
	
	/**
	 * @throws Exception if there was a problem with the prime generator
	 * @note this could entirely be replaced by just adding the first 10 primes hardcoded
	 */
	public Problem62() throws Exception
	{
		// one prime for each digit
		_primes = new long[10];
		// prime generator
		IPrimes primes = PrimesFactory.getSieve();
		// start looking for primes
		long p = 1;
		for (int i = 0; i < 10; ++i)
		{
			p = primes.generatePrime(p);
			_primes[i] = p;
		}
	}
	
	/**
	 * @param p number to generate hash for
	 * @return the hash value of p (generated by multiplying the values of each digit as indices in the primes array)
	 * @note the hash value has to be unique for the combination of digits in the number (H(12345) == H(24513))
	 */
	public long getPrimeHash(long p)
	{
		// convert the number to its digits
		int[] n = Digits.Number(p);
		long hash = 1;
		
		// now multiply each digits using its index prime value
		for (int i: n)
			hash *= _primes[i];
		
		return hash;
	}
	
	/**
	 * @return the smallest cube that has 5 permutations that are also cubes
	 * @throws Exception if no solution can be found
	 */
	public long getSolution() throws Exception {
		// store the primes and their hashes in a tree map
		TreeMap<Long, ArrayList<Long>> tm = new TreeMap<Long, ArrayList<Long>>();
		
		// hopefully the solution will be found in less than 10000 cubes
		for (long n = 1L; n < 10000; ++n)
		{
			// calculate the cube
			long pow3 = (long)Math.pow(n, 3);
			// get the hash of the cube
			long hash = getPrimeHash(pow3);
			
			// check if there was already a number with this hash
			if (tm.containsKey(hash))
			{
				// add the cube to the stored list of cubes
				ArrayList<Long> existingList = tm.get(hash);
				existingList.add(pow3);
				tm.remove(hash);
				tm.put(hash,  existingList);
			}
			else
			{
				// create a new list for the cubes of this hash
				ArrayList<Long> newList = new ArrayList<Long>();
				newList.add(pow3);
				tm.put(hash, newList);
			}
		}
		
		long min = Long.MAX_VALUE;
		// now just check if any hash has 5 entries in its list
		for (Entry<Long, ArrayList<Long>> e: tm.entrySet())
		{
			if (e.getValue().size() == 5)
			{
				// if there are more than one make sure the minimum is returned
				if (min > e.getValue().get(0))
					min = e.getValue().get(0);
			}
		}
		if (min != Long.MAX_VALUE)
			return min;
		throw new Exception("no solution found");
	}

}
